package array;

import java.util.Map.Entry;

public class DistanceMax {
	
	//Given an array arr[], find the maximum j  i such that arr[j] > arr[i].
	public static void MaxDiff(int[] array)
	{
		int left = 0;
		int right = 0;
		int n = array.length;
		int[] lMin = new int[n];
		int[] rMax = new int[n];
		
		
		/* Construct LMin[] such that LMin[i] stores the minimum value
	       from (arr[0], arr[1], ... arr[i]) */
		lMin[0] = array[0];
		for(int i = 1; i < n; i++){
				lMin[i] = Math.min(array[i], lMin[i-1]);
		}
		/* Construct RMax[] such that RMax[j] stores the maximum value
	       from (arr[j], arr[j+1], ..arr[n-1]) */
		rMax[n-1] = array[n-1];
		for(int i = n-2; i >= 0; i--){
			rMax[i] = Math.max(array[i], rMax[i+1]);
		}
		int maxdiff = 0;
		int i = 0;
		int j = 0;
		
		/* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
		while(i < n && j < n){
			if(lMin[i] < rMax[j]){
				if(j - i > maxdiff){
					maxdiff = j - i;
					left = i;
					right = j;
				}
				j++;
			}else
				i++;
		
		}
		System.out.println(left + " " + right); 
		
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array = {34, 8, 10, 3, 2, 80, 30, 33, 1};
		MaxDiff(array);
	}
}
